package com.duoduo.树;

import com.duoduo.TreeNode;

import java.util.*;

/**
 * @program: algorithm
 * @description: 二叉树的后序遍历145
 *给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *
 * 入：root = [1,null,2,3]
 * 输出：[3,2,1]
 * @author: chaidl  ！
 * @create: 2022-04-11 15:26
 */
//[ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。
public class 二叉树的后序遍历145 {
	public List<Integer> postorderTraversal2(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		Deque<TreeNode> stack=new LinkedList<>();
		TreeNode tmp=null;
		while (root!=null || !stack.isEmpty()){
			while (root != null){
				stack.push(root);
				root=root.left;
			}
		//	到这一步的时候表示已经到了最左边的子节点，出栈
			root=stack.pop();
			if (root.right==null || root.right==tmp){
				result.add(root.val);
				tmp=root;
				root=null;
			}else {
				stack.push(root);
				root=root.right;
			}
		}
		return result;
	}
	public List<Integer> postorderTraversal(TreeNode root) {
		List<Integer> result=new ArrayList<Integer>();
		accessTree(root,result);
		return result;
	}
	
	private void accessTree(TreeNode root, List<Integer> result) {
		if (root == null) {
		    return;
		}
		accessTree(root.left,result);
		accessTree(root.right,result);
		result.add(root.val);
	}

	//比较慢的迭代
	public List<Integer> postorderTraversal3(TreeNode root) {
		List<Integer> result=new ArrayList<>();
		if (root == null){
			return result;
		}
		Deque<TreeNode> stack=new LinkedList<>();
		// 压栈  中->左->右
		stack.push(root);
		while(!stack.isEmpty()){
			// 出栈 中->右->左
			TreeNode node = stack.pop();
			result.add(node.val);
			if (node.left != null){
				stack.push(node.left);
			}
			if (node.right != null){
				stack.push(node.right);
			}
		}
		// 倒序后 左->右——>中
		Collections.reverse(result);
		return result;
	}
}
